



#include"stl_union.h"

#include<stdlib.h>


/// <summary>
/// 分配并查集内存。
/// </summary>
/// <param name="u"></param>
/// <param name="size"></param>
void union_allocate(Union* u, int size)
{
	u->sets = (int*)malloc(size * sizeof(int));
	u->size = size;
}

/// <summary>
/// 释放并查集内存
/// </summary>
/// <param name="u"></param>
void union_deallocate(Union* u)
{
	free(u->sets);
	u->size = 0;
}

/// <summary>
/// 初始化并查集内存。
/// </summary>
/// <param name="u"></param>
void union_init(Union* u)
{
	for (int i = 0; i < u->size; i++) {
		u->sets[i] = -1;
	}
}

/// <summary>
/// 寻找元素的根节点序号
/// </summary>
/// <param name="u">并查集</param>
/// <param name="element">元素序号</param>
/// <returns>根节点索引</returns>
int union_find_root(Union* u, int element) {
	int root = element;
	while (u->sets[root] >= 0)
	{
		root = u->sets[root];  // 寻找路径
	}	// 此时u->sets[root] 是根节点。

	while (element != root) {  // 压缩路径，将根到x路径上的节点都变成集合根的孩子。
		int t = u->sets[element];  // t是元素的根节点。
		u->sets[element] = root;   // 元素根节点指向集合的根。
		element = t;
	}
	return root;
}

/// <summary>
/// root1，root2必须是根节点，否则并查集的结构会被破坏。
/// 使用union_find_root 可以找到元素的根节点。
/// </summary>
/// <param name="u">并查集</param>
/// <param name="root1">子集根节点</param>
/// <param name="root2">子集根节点</param>
/// <returns>根节点元素数量</returns>
int union_union(Union* u, int root1, int root2) {
	if (root1 == root2)return -u->sets[root1];
	if (u->sets[root1] < u->sets[root2]) {
		u->sets[root1] += u->sets[root2];  // 小树合并大树
		u->sets[root2] = root1;
		return -u->sets[root1];
	}
	else
	{
		u->sets[root2] += u->sets[root1];  // 小树合并大树
		u->sets[root1] = root2;
		return -u->sets[root2];
	}
}



